package cn.lishiyuan.algorithm.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.function.Function;

/**
 * 计数排序
 * <br>
 * 计数排序是桶排序的优化，它对数据的要求要比桶排序还要更高。
 * <br>
 * 计数排序的思路是，对数据范围数据映射到线性表index，每个index里面的item都是小于等于该index值的数量。
 * <br>
 * 先扫描一边进行计数，再扫描一边进行排序也就是位置确定。
 */
public class CountingSort {

    public <T extends Comparable<T>> List<T> sort(List<T> data,Function<T, Integer> map) {
        List<Integer> buckets = new ArrayList<>();
        // 第一遍扫描进行计数
        for (T datum : data) {
            Integer bucketIndex = map.apply(datum);

            while (buckets.size() <= bucketIndex) {
                buckets.add(0);
            }
            Integer count = buckets.get(bucketIndex);
            if (count == null) {
                count = 0;
                buckets.set(bucketIndex,count);
            }
            count++;
            buckets.set(bucketIndex,count);
        }

        // 对countData进行向后加
        for (int i = 1; i < buckets.size(); i++) {
            int before = i-1;
            Integer now = buckets.get(i);
            Integer beforeValue = buckets.get(before);
            buckets.set(i,beforeValue + now);
        }

        // 直接插入null
        List<T> result = new ArrayList<>(Collections.nCopies(data.size(), null));

        // 第二遍扫描确认位置进行排序，从后向前，保证稳定
        for (int i = data.size() - 1; i >= 0; i--){
            T datum = data.get(i);
            Integer bucketIndex = map.apply(datum);
            Integer count = buckets.get(bucketIndex);

            result.set(count - 1,datum);
            count--;
            buckets.set(bucketIndex,count);
        }

        return result;
    }
}
